leetcode/124. Binary Tree Maximum Path Sum.c at master · vli02/leetcode · GitHub

Name: leetcode/124. Binary Tree Maximum Path Sum.c at master · vli02/leetcode · GitHub
Rating: 4.9 (6442 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.


For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.


For example:
Given the below binary tree,
 1
 / \
 2 3


Return 6.
*/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * struct TreeNode *left;
 * struct TreeNode *right;
 * };
 */
intmaxsum(structTreeNode*node, int*max) {
intl, r, k, s;

if (!node) return0;

l=maxsum(node->left, max);
r=maxsum(node->right, max);

l=l>0 ? l : 0; // ignore negative
r=r>0 ? r : 0;

s=node->val+l+r; // current node + both sides
if (*max<s) *max=s;

k=node->val+ (l>r ? l : r); // current node + one side only
returnk;
}
intmaxPathSum(structTreeNode*root) {
intmax;
if (root) {
max=root->val;
maxsum(root, &max);
 } else {
max=0;
 }
returnmax;
}


/*
Difficulty:Hard
Total Accepted:101.3K
Total Submissions:388.5K


Companies Microsoft Baidu
Related Topics Tree Depth-first Search
Similar Questions


 Path Sum

 Sum Root to Leaf Numbers
*/